package merge

import (
	"slices"
)

/*
基数排序（英语：Radix sort）是一种非比较型的排序算法，最早用于解决卡片排序的问题。基数排序将待排序的元素拆分为 k 个关键字，逐一对各个关键字排序后完成对所有元素的排序。
如果是从第 1 关键字到第 k 关键字顺序进行比较，则该基数排序称为 MSD（Most Significant Digit first）基数排序；
如果是从第 k 关键字到第 1 关键字顺序进行比较，则该基数排序称为 LSD（Least Significant Digit first）基数排序。

数排序（radixsort）的核心思想与计数排序一致，也通过统计个数来实现排序。在此基础上，基数排序利
用数字各位之间的递进关系，依次对每一位进行排序，从而得到最终的排序结果。
相同8位數字,按照每一位個 十 百 千 萬等等 依次排序

，但前提是数据必须可以表示为固定位数的格式，且位
数不能过大。例如，浮点数不适合使用基数排序，因为其位数𝑘过大，可能导致时间复杂度𝑂(𝑛𝑘)≫𝑂(𝑛2)
。
‧ 时间复杂度为𝑂(𝑛𝑘)、非自适应排序：设数据量为𝑛、数据为𝑑进制、最大位数为𝑘，则对某一位执
行计数排序使用𝑂(𝑛+𝑑)时间，排序所有𝑘位使用𝑂((𝑛+𝑑)𝑘)时间。通常情况下，𝑑和𝑘都相对
较小，时间复杂度趋向𝑂(𝑛)。
‧ 空间复杂度为𝑂(𝑛+𝑑)、非原地排序：与计数排序相同，基数排序需要借助长度为𝑛和𝑑的数组
res
和counter。
‧ 稳定排序：当计数排序稳定时，基数排序也稳定；当计数排序不稳定时，基数排序无法保证得到正确的
排序结果

*/

type radix struct {
}

// === File: radix_sort.go ===
/* 获取元素 num 的第 k 位，其中 exp = 10^(k-1) */
func (r radix) digit(num, exp int) int {
	// 传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算
	return (num / exp) % 10
}

/* 计数排序（根据 nums 第 k 位排序） */
func (r radix) countingSortDigit(nums []int, exp int) {
	// 十进制的位范围为 0~9 ，因此需要长度为 10 的桶数组
	counter := make([]int, 10)
	n := len(nums)
	// 统计 0~9 各数字的出现次数
	for i := 0; i < n; i++ {
		d := r.digit(nums[i], exp) // 获取 nums[i] 第 k 位，记为 d
		counter[d]++
		// 统计数字 d 的出现次数
	}
	// 求前缀和，将“出现个数”转换为“数组索引”
	for i := 1; i < 10; i++ {
		counter[i] += counter[i-1]
	}
	// 倒序遍历，根据桶内统计结果，将各元素填入 res
	res := make([]int, n)
	for i := n - 1; i >= 0; i-- {
		d := r.digit(nums[i], exp)
		j := counter[d] - 1 // 获取 d 在数组中的索引 j
		res[j] = nums[i]
		// 将当前元素填入索引 j
		counter[d]--
		// 将 d 的数量减 1
	}
	// 使用结果覆盖原数组 nums
	for i := 0; i < n; i++ {
		nums[i] = res[i]
	}
}

/* 基数排序 */
func (r radix) radixSort(nums []int) {
	// 获取数组的最大元素，用于判断最大位数
	maxNum := slices.Max(nums)
	// 按照从低位到高位的顺序遍历
	for exp := 1; maxNum >= exp; exp *= 10 {
		// 对数组元素的第 k 位执行计数排序
		// k = 1-> exp = 1
		// k = 2-> exp = 10
		// 即 exp = 10^(k-1)
		r.countingSortDigit(nums, exp)
	}
}
